1. Technical Field
Apparatuses and methods consistent with the present invention relate to arithmetic decoding, and more particularly, to high-speed arithmetic decoding using a prediction technique.
2. Related Art
Image data is very large in size, and therefore, compression coding is required to store or transmit the image data. Arithmetic coding, which is an image data compression technique, arithmetically computes the range of a cumulative distribution function for a stream of input symbols. As a result, a codeword corresponding to the range of the cumulative distribution function is automatically acquired. Accordingly, it is possible to easily code even a long stream of input symbols.
The related art MPEG-4 Part 10 advanced video coding (AVC) standard, which is a video compression standard, has higher coding efficiency than the related art MPEG-4 Part 2 visual codec standard, and is designed to be robust with respect to errors and be network-friendly in consideration of rapidly changing wire and Internet environments.
The related art MPEG-4 Part 10 AVC standard adopts context adaptive binary arithmetic coding (CABAC) which is a type of arithmetic coding. CABAC is binary arithmetic coding to which context, that is, dynamic statistical characteristics, is applied. Since a related art entropy coder uses static statistics, the coding performance of the entropy coder is degraded when data with characteristics different from predetermined statistical characteristics is generated during decoding. That is, at least one bit is required even if generation of the symbol is expected with a very high probability and the symbol is substantially coded. For instance, even when a probability that a symbol “a” would be coded through Huffman coding is 0.99, a bit must be allocated to the symbol “a” to code the symbol “a”.
CABAC uses binary arithmetic coding. One of the advantages of arithmetic coding is that it does not require integer bits of data to code a symbol. When the symbol “a” with the coding probability of 0.99 is coded continuously five times through Huffman coding, for example, it is possible to code the symbol “a” to only 1 bit through arithmetic coding. That is, each symbol can be coded to a 0.2 bit.
Related art CABAC encoding according to the MPEG-4 Part 10 AVC standard will briefly be described. First, binarization by which input data is transformed into binary values using various methods is performed. Since symbols are processed as binary values in CABAC, all data values must be transformed into binary values before performing arithmetic coding. Syntax elements obtained as a result of video processing may not be binary values. In this case, the syntax elements are transformed into binary values using various binarization methods. In CABAC according to the MPEG-4 Part 10 AVC standard, four binarization methods are defined.
When distributions of values of 0's or 1's obtained by binarizing the syntax elements are substantially the same, coding efficiencies of arithmetic coding to be performed on the syntax elements are also expected to be the same. Accordingly, the syntax elements are bypassed without being coded.
If the distribution of binary values converges on a specific symbol, arithmetic coding is performed as follows. First, the type of probability distribution for each coding stage is determined through context modeling. Context modeling is performed differently according to the type of a syntax element, the ordinal number of a symbol to which the syntax element corresponds in syntax, and the distribution of already-decoded values. Context modeling is performed to exactly predict the probable characteristics of a symbol that is currently being decoded. More specifically, context is comprised of the value of a most probable symbol (MPS) and the probabilities of a least probable symbol (LPS). Since binarization is performed before context modeling, the value of the MPS or the value of the LPS is 0 or 1. Thus, when the value of the MPS is determined, the value of the LPS is automatically determined, and when the probability of the LPS is determined, the probability of the MPS is computed by subtracting the probability of the LPS from 1. In general, the lower the probability of the LPS and the more the MPS is decoded, the higher the compression efficiency of CABAC.
When the value of the MPS and the probability of the LPS are determined through context modeling, a codeword is also determined. Arithmetic coding is performed while limiting the range of coding during data compression without continuously outputting a specific codeword. One of a lower bound, an upper bound, and a difference range between the lower range and the upper range is determined as the codeword. Also, the lower bound, or a value that can be represented with the smallest bit within a predetermined range, is determined as the codeword. In CABAC, the lower bound is determined to be the codeword.
A related art CABAC decoding process according to the MPEG-4 Part 10 AVC will now be described. FIG. 1 is a block diagram of a related art CABAC decoder. Three values, i.e., a context index, a range, and an offset, are required to decode a current symbol. Referring to FIG. 1, an LPS probability (k), an MPS value (k), a Range (k), and an Offset (k) are input to a binary arithmetic decoding unit 130 to decode a kth symbol S(k). The LPS probability (k) and the MPS value (k) corresponding to a context index (k) determined through context modeling are read from a memory 110. A method of acquiring the LPS probability (k) and the MPS value (k) from the context index (k) is described in greater detail in the related art MPEG-4 Part 10 AVC standard.
The range R(k,LPS) of the LPS is determined using the LPS probability (k) and the Range (k) as key values, based on an LPS range table. The range R(k,MPS) of the MPS is determined by subtracting the range R(k,LPS) of the LPS from the Range (k).
FIG. 2 illustrates a probability distribution section that includes the range R(k,LPS) of the LPS and the range R(k,MPS) of the MPS. The ranges R(k,LPS) and R(k,MPS) indicate the lengths of probability distribution sections of the LPS and the MPS respectively, not upper and lower bounds of the probability distribution sections of the LPS and the MPS.
After obtaining the range R(k,MPS), the range R(k,MPS) and the Offset (k) are compared. When the Offset (k) is equal to or greater than the range R(k,MPS), the kth symbol S(k) is determined to be the value of the LPS. When the Offset (k) is less than the range R(k,MPS), the kth symbol S(k) is determined to be the value of the MPS. After decoding the kth symbol S(k), a new Range (k+1) and a new Offset (k+1) required for decoding the next symbol S(k+1) are determined. That is, when the kth symbol S(k) is determined as the value of the MPS, the new range Range(k+1) and the new Offset (k+1) are determined to be R(k,MPS) and Offset(k), respectively.
However, when the kth symbol S(k) is the value of the LPS, the new range Range(k+1) is determined to be R(k,LPS) and the new Offset (k+1) is a value obtained by subtracting the range R(k,MPS) from the Offset (k), since a lower bound of range is newly determined.
The ranges of the LPS and the MPS cannot be computed with unlimited precision and thus are limited to predetermined bits, i.e., 9 bits. To prevent the ranges from reducing to 0, they are always controlled to fall within a predetermined range from 0×0100 to 0×01fe before decoding a new symbol. If a range used to symbol decoding is out of the predetermined range, the range is adjusted to fall within the predetermined range through renormalization. When the range is readjusted, an offset corresponding to the range also is readjusted. Renormalization of the range and the offset is performed using a shift operation. The offset is shifted by the degree of shifting the range.
When renormalization is completed, the new range Range(k+1) and the new offset Offset(k+1) required for decoding the next symbol S(k+1) are prepared. The new range Range(k+1) and the new offset Offset(k+1) are input to the binary arithmetic decoding unit 130. The binary arithmetic decoding unit 130 is further given the LPS probability(k+1) and the MPS value(k+1) corresponding to a context Index(k+1) determined through context modeling to decode the next symbol S(k+1), and decodes the next symbol in the same manner in which the kth symbol S(k) is decoded.
As described above, in CABAC, by applying statistical characteristics dynamically, a probability to be applied to each symbol can be precisely predicted, and by compressing data to non-integer bits, compression efficiency can be increased. However, the complexity of CABAC is very high since context modeling is required and a range and an offset must be updated whenever each input symbol is coded or decoded. Therefore, development of a high-speed CABAC encoder and decoder is required to increase overall encoding and decoding performance. Further, as described above, in related art arithmetic coding and decoding, a range and offset required to decode a next symbol can be determined only after decoding a current symbol, thereby making it difficult to decode a plurality of symbols in parallel.